class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        n = len(rains)
        ans = [-1] * n
        full_day = {}  # lake -> 装满日
        dry_day = SortedList()  # 未被使用的抽水日
        for i, lake in enumerate(rains):
            if lake == 0:
                ans[i] = 1  # 先随便选一个湖抽干
                dry_day.add(i)  # 保存抽水日
                continue
            if lake in full_day:
                j = full_day[lake]
                # 必须在 j 之后，i 之前把 lake 抽干
                # 选一个最早的未被使用的抽水日，如果选晚的，可能会导致其他湖没有可用的抽水日
                k = dry_day.bisect_right(j)
                if k == len(dry_day):
                    return []  # 无法阻止洪水
                d = dry_day[k]
                ans[d] = lake
                dry_day.discard(d)  # 移除已使用的抽水日
            full_day[lake] = i  # 插入或更新装满日
        return ans


# 并查集
class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        n = len(rains)
        # 非递归并查集
        fa = list(range(n + 1))
        def find(x: int) -> int:
            rt = x
            while fa[rt] != rt:
                rt = fa[rt]
            while fa[x] != rt:
                fa[x], x = rt, fa[x]
            return rt

        ans = [-1] * n
        full_day = {}  # lake -> 装满日
        for i, lake in enumerate(rains):
            if lake == 0:
                ans[i] = 1  # 先随便选一个湖抽干
                continue
            if lake in full_day:
                j = full_day[lake]
                # 必须在 j 之后，i 之前把 lake 抽干
                # 选一个最早的未被使用的抽水日，如果选晚的，可能会导致其他湖没有可用的抽水日
                dry_day = find(j + 1)
                if dry_day >= i:
                    return []  # 无法阻止洪水
                ans[dry_day] = lake
                fa[dry_day] = find(dry_day + 1)  # 删除 dry_day
            fa[i] = i + 1  # 删除 i
            full_day[lake] = i  # 插入或更新装满日
        return ans
